#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<iostream>
using namespace std;
int BinarySearch(int arr[], int size, int val) {
	int first = 0;
	int last = size - 1;
	while (first <= last) {
		int middle = last + (first - last) / 2;
		if (arr[middle] > val)
			last = last - 1;
		else if (arr[middle] < val) {
			first = first - 1;
		}
		else {
			return middle;  
		}
	}
}